package com.bear.线性结构.单链表;

import java.util.Stack;

/**
 * <简述>
 * <详细描述>
 *
 * @author LiuShanshan
 * @version $Id$
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        // 测试
        SingleLinked singleLinked = new SingleLinked();
        singleLinked.addByNo(new HeroNode(1, "宋江"));
        singleLinked.addByNo(new HeroNode(4, "林冲"));
        singleLinked.addByNo(new HeroNode(2, "卢俊义"));
        singleLinked.addByNo(new HeroNode(3, "吴用"));
        singleLinked.addByNo(new HeroNode(3, "吴用2"));
        singleLinked.show();

        // 显示长度
        int length = singleLinked.getLength();
        System.out.println(length);
        // 查询出倒数第2个元素的数据
        HeroNode heroNode = singleLinked.selectReciIndex(4);
        System.out.println(heroNode);

        // ================================================将链表倒转===============
        System.out.println("================================================将链表倒转===============");
        // 单项链表倒转，实现原理：创建一个单链表倒叙数据，将链表循环，每一次循环的数据作为倒转链表的next值，
        // 倒叙链表的next值作为传过来的数据的next值
        singleLinked.reverse();
        singleLinked.show();

        //============================链表倒叙打印=================
        System.out.println("============================链表倒叙打印=================");
        singleLinked.stack();
    }
}
// 单链表 处理类
class SingleLinked{
    // head信息，在链表的第一个，不能变动
    private HeroNode heroNodeHeard  = new HeroNode(0, "");

    // 添加
    public void addByNo(HeroNode heroNode){
        // 添加辅助节点
        HeroNode temp = heroNodeHeard;
        boolean isRep = false;
        while (true){
            // 当前节点next为null,退出
            if(temp.next == null){
                break;
            }
            // 当前节点next值的no值大于传入进来的heroNode中的no值（因为是从小到大排序），则退出
            if(temp.next.no > heroNode.no){
                break;
            }else if (temp.next.no == heroNode.no){
                isRep = true;
            }
            temp = temp.next;
        }
        if(isRep){
            System.out.println("有重复数据，报错.");
        }else{
            // 到了这里，temp中的next就应该放入参heroNode
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //显示
    public void show(){
        if(heroNodeHeard.next == null){
            System.out.println("没有添加数据");
        }else{
            // 头信息不能动
            HeroNode temp = heroNodeHeard.next;
            while (true){
                System.out.println(temp);
                if(temp.next == null){
                    break;
                }
                temp = temp.next;
            }
        }
    }

    // 显示长度  heroNodeHeard 为头节点
    public int getLength()  {
        // next没值返回0
        if(heroNodeHeard.next == null){
            return 0;
        }
        // next有值进行循环
        int size = 0;
        HeroNode temp = heroNodeHeard.next;
        while (true){
            size ++;
            if(temp.next != null){
                temp = temp.next;
            }else{
                break;
            }
        }
        return size;
    }

    // 查找单链表中的倒数第k个结点
    public HeroNode selectReciIndex(int index){
        // index是否合理            // index不能比长度大
        if(index <= 0 || index > getLength()){
            return null;
        }
        // 用长度减去index，得到应该查询第几条数据
        int shouldSelectLength = getLength() - index + 1;
        // 进行循环，查找到数据
        HeroNode temp = heroNodeHeard.next;
        for (int i = 1; i < shouldSelectLength; i++){
            temp = temp.next;
        }
        return temp;
    }

    // 倒转链表
    public void reverse(){
        // 定义一个辅助变量，帮助我们遍历原来的链表
        HeroNode cur = heroNodeHeard.next;
        HeroNode next = null;     // 指向当前节点[cur]的下一个节点
        // 倒转数组
        HeroNode reverseHead = new HeroNode(0, "");
        // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        while(cur != null){
            next = cur.next;
            // 将倒转数据下面的next给cur,因为cur将会成为倒转数组里面的第一个数据
           cur.next = reverseHead.next;
           reverseHead.next = cur;
           cur = next;
        }
        // 赋值，将revers中的next放入head的next中, head.next = reverse.next
        heroNodeHeard.next = reverseHead.next;
    }

    //  链表倒叙输出    方法1：使用倒转链表的方法；方法2：使用栈的方式stack
    public void stack(){
        Stack<HeroNode> heroNodeStack = new Stack<HeroNode>();
        HeroNode next = heroNodeHeard.next;
        while(next != null){
            heroNodeStack.push(next);
            next = next.next;
        }
        while (heroNodeStack.size()>0){
            System.out.println(heroNodeStack.pop());
        }
    }

}



// 类
class HeroNode{
    // 编号
    public int no;
    // 名称
    public String name;
    // 指向下一个元素的对象
    public HeroNode next;
    // 指向上一个元素的对象
    public HeroNode pre;
    HeroNode(int no, String name){
        this.no = no;
        this.name = name;
    }



    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}
